# -*- coding: utf-8 -*-


def gcd(a, b):
    if b == 0:
        x1 = 1
        y1 = 0
        x = x1
        y = y1
        r = a
        return r, x, y
    else:
        r, x1, y1 = gcd(b, a % b)
        x = y1
        y = x1 - a // b * y1
        return r, x, y
